package SubjectTree.Two;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import Utility.Node;

public class MaxDepth2 {

/**
 * 难度：简单
 * 
 * 559. N 叉树的最大深度
 * 	给定一个 N 叉树，找到其最大深度。
 * 	最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
 * 	N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
 * 	
 * 示例 1：
 * 	输入：root = [1,null,3,2,4,null,5,6]
 * 	输出：3
 * 	
 * 示例 2：
 * 	输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 * 	输出：5
 * 	
 * 提示：
 * 	树的深度不会超过 1000 。
 * 	树的节点数目位于 [0, 104] 之间。
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<Node> list = new ArrayList<>();
		List<Node> list2 = new ArrayList<>();
		MaxDepth2 md2 = new MaxDepth2();
		Node node = new Node(1);
		node.children = list;
		Node node3 = new Node(3);
		node3.children = list2;
		list.add(new Node(2));
		list.add(new Node(4));
		list.add(node3);
		list2.add(new Node(5));
		list2.add(new Node(6));
		System.out.println(md2.maxDepth1(node));
	}
	//自己写（逐层遍历）
	public int maxDepth(Node root) {
        if(root==null)return 0;
        Deque<Node> deque = new LinkedList<>();
        deque.offer(root);
        int count = 0;
        while(!deque.isEmpty()) {
        	int currentLevelSize = deque.size();
        	for(int i=0;i<currentLevelSize;i++) {
        		Node node = deque.poll();
        		if(node.children!=null) {
        			node.children.stream().forEach(n->deque.offer(n));
        		}
        	}
        	count++;
        }
		return count;
    }
	//自己写（递归,使用后续遍历）
	public int maxDepth_1(Node root) {
		if(root==null)return 0;
		int count = 0;
		if(root.children!=null){
			for(Node n:root.children) {
				count = Math.max(count, maxDepth_1(n));
			}
		}
		return count + 1;
	}
	//方法一: 递归
	public int maxDepth1(Node root) {
	    if (root == null) {
	    	return 0;
	    } else if (root.children.isEmpty()) {
	    	return 1;  
	    } else {
	    	List<Integer> heights = new LinkedList<>();
	    	for (Node item : root.children) {
	    		heights.add(maxDepth(item)); 
	    	}
	    	return Collections.max(heights) + 1;
	    }
	}
	//方法二: 迭代
//	public int maxDepth2(Node root) {
//	    Queue<Pair<Node, Integer>> stack = new LinkedList<>();
//	    if (root != null) {
//	      stack.add(new Pair(root, 1));
//	    }
//
//	    int depth = 0;
//	    while (!stack.isEmpty()) {
//	      Pair<Node, Integer> current = stack.poll();
//	      root = current.getKey();
//	      int current_depth = current.getValue();
//	      if (root != null) {
//	        depth = Math.max(depth, current_depth);
//	        for (Node c : root.children) {
//	          stack.add(new Pair(c, current_depth + 1));    
//	        }
//	      }
//	    }
//	    return depth;
//	}
}
